#include<stdio.h>
#include<iostream>
#include<fstream>
#include<iomanip>
#include <string>

using namespace std;
#define len1 128 
#define len2 32

/*前2800个素数(从3开始)，用于素数测试，被判断的大数先除于这2800个小素数来提高测试的效率
附上产生前2800个素数的代码
#include<stdio.h>
#include<stdlib.h>
int isprime(int num);
main()
{
     int i=0,N=3;
     while(i<2800){
        if(!isprime(N)){
           i++;
           printf("%d\t",N);
        }
        N++;
    }
    system("pause");
    return 0;
}

int isprime(int num)
{
    int i;
    
    for(i=2;i<=num;i++)
       
       if(num%i==0){
          if(num!=i)
             return 1;//不是素数 
          else
             return 0;//是素数 
       }
}*/
static int Primes[2800]=                         //前2800个素数 
{
3,      5,      7,      11,     13,     17,     19,     23,     29,     31,
37,     41,     43,     47,     53,     59,     61,     67,     71,     73,
79,     83,     89,     97,     101,    103,    107,    109,    113,    127,
131,    137,    139,    149,    151,    157,    163,    167,    173,    179,
181,    191,    193,    197,    199,    211,    223,    227,    229,    233,
239,    241,    251,    257,    263,    269,    271,    277,    281,    283,
293,    307,    311,    313,    317,    331,    337,    347,    349,    353,
359,    367,    373,    379,    383,    389,    397,    401,    409,    419,
421,    431,    433,    439,    443,    449,    457,    461,    463,    467,
479,    487,    491,    499,    503,    509,    521,    523,    541,    547,
557,    563,    569,    571,    577,    587,    593,    599,    601,    607,
613,    617,    619,    631,    641,    643,    647,    653,    659,    661,
673,    677,    683,    691,    701,    709,    719,    727,    733,    739,
743,    751,    757,    761,    769,    773,    787,    797,    809,    811,
821,    823,    827,    829,    839,    853,    857,    859,    863,    877,
881,    883,    887,    907,    911,    919,    929,    937,    941,    947,
953,    967,    971,    977,    983,    991,    997,    1009,   1013,   1019,
1021,   1031,   1033,   1039,   1049,   1051,   1061,   1063,   1069,   1087,
1091,   1093,   1097,   1103,   1109,   1117,   1123,   1129,   1151,   1153,
1163,   1171,   1181,   1187,   1193,   1201,   1213,   1217,   1223,   1229,
1231,   1237,   1249,   1259,   1277,   1279,   1283,   1289,   1291,   1297,
1301,   1303,   1307,   1319,   1321,   1327,   1361,   1367,   1373,   1381,
1399,   1409,   1423,   1427,   1429,   1433,   1439,   1447,   1451,   1453,
1459,   1471,   1481,   1483,   1487,   1489,   1493,   1499,   1511,   1523,
1531,   1543,   1549,   1553,   1559,   1567,   1571,   1579,   1583,   1597,
1601,   1607,   1609,   1613,   1619,   1621,   1627,   1637,   1657,   1663,
1667,   1669,   1693,   1697,   1699,   1709,   1721,   1723,   1733,   1741,
1747,   1753,   1759,   1777,   1783,   1787,   1789,   1801,   1811,   1823,
1831,   1847,   1861,   1867,   1871,   1873,   1877,   1879,   1889,   1901,
1907,   1913,   1931,   1933,   1949,   1951,   1973,   1979,   1987,   1993,
1997,   1999,   2003,   2011,   2017,   2027,   2029,   2039,   2053,   2063,
2069,   2081,   2083,   2087,   2089,   2099,   2111,   2113,   2129,   2131,
2137,   2141,   2143,   2153,   2161,   2179,   2203,   2207,   2213,   2221,
2237,   2239,   2243,   2251,   2267,   2269,   2273,   2281,   2287,   2293,
2297,   2309,   2311,   2333,   2339,   2341,   2347,   2351,   2357,   2371,
2377,   2381,   2383,   2389,   2393,   2399,   2411,   2417,   2423,   2437,
2441,   2447,   2459,   2467,   2473,   2477,   2503,   2521,   2531,   2539,
2543,   2549,   2551,   2557,   2579,   2591,   2593,   2609,   2617,   2621,
2633,   2647,   2657,   2659,   2663,   2671,   2677,   2683,   2687,   2689,
2693,   2699,   2707,   2711,   2713,   2719,   2729,   2731,   2741,   2749,
2753,   2767,   2777,   2789,   2791,   2797,   2801,   2803,   2819,   2833,
2837,   2843,   2851,   2857,   2861,   2879,   2887,   2897,   2903,   2909,
2917,   2927,   2939,   2953,   2957,   2963,   2969,   2971,   2999,   3001,
3011,   3019,   3023,   3037,   3041,   3049,   3061,   3067,   3079,   3083,
3089,   3109,   3119,   3121,   3137,   3163,   3167,   3169,   3181,   3187,
3191,   3203,   3209,   3217,   3221,   3229,   3251,   3253,   3257,   3259,
3271,   3299,   3301,   3307,   3313,   3319,   3323,   3329,   3331,   3343,
3347,   3359,   3361,   3371,   3373,   3389,   3391,   3407,   3413,   3433,
3449,   3457,   3461,   3463,   3467,   3469,   3491,   3499,   3511,   3517,
3527,   3529,   3533,   3539,   3541,   3547,   3557,   3559,   3571,   3581,
3583,   3593,   3607,   3613,   3617,   3623,   3631,   3637,   3643,   3659,
3671,   3673,   3677,   3691,   3697,   3701,   3709,   3719,   3727,   3733,
3739,   3761,   3767,   3769,   3779,   3793,   3797,   3803,   3821,   3823,
3833,   3847,   3851,   3853,   3863,   3877,   3881,   3889,   3907,   3911,
3917,   3919,   3923,   3929,   3931,   3943,   3947,   3967,   3989,   4001,
4003,   4007,   4013,   4019,   4021,   4027,   4049,   4051,   4057,   4073,
4079,   4091,   4093,   4099,   4111,   4127,   4129,   4133,   4139,   4153,
4157,   4159,   4177,   4201,   4211,   4217,   4219,   4229,   4231,   4241,
4243,   4253,   4259,   4261,   4271,   4273,   4283,   4289,   4297,   4327,
4337,   4339,   4349,   4357,   4363,   4373,   4391,   4397,   4409,   4421,
4423,   4441,   4447,   4451,   4457,   4463,   4481,   4483,   4493,   4507,
4513,   4517,   4519,   4523,   4547,   4549,   4561,   4567,   4583,   4591,
4597,   4603,   4621,   4637,   4639,   4643,   4649,   4651,   4657,   4663,
4673,   4679,   4691,   4703,   4721,   4723,   4729,   4733,   4751,   4759,
4783,   4787,   4789,   4793,   4799,   4801,   4813,   4817,   4831,   4861,
4871,   4877,   4889,   4903,   4909,   4919,   4931,   4933,   4937,   4943,
4951,   4957,   4967,   4969,   4973,   4987,   4993,   4999,   5003,   5009,
5011,   5021,   5023,   5039,   5051,   5059,   5077,   5081,   5087,   5099,
5101,   5107,   5113,   5119,   5147,   5153,   5167,   5171,   5179,   5189,
5197,   5209,   5227,   5231,   5233,   5237,   5261,   5273,   5279,   5281,
5297,   5303,   5309,   5323,   5333,   5347,   5351,   5381,   5387,   5393,
5399,   5407,   5413,   5417,   5419,   5431,   5437,   5441,   5443,   5449,
5471,   5477,   5479,   5483,   5501,   5503,   5507,   5519,   5521,   5527,
5531,   5557,   5563,   5569,   5573,   5581,   5591,   5623,   5639,   5641,
5647,   5651,   5653,   5657,   5659,   5669,   5683,   5689,   5693,   5701,
5711,   5717,   5737,   5741,   5743,   5749,   5779,   5783,   5791,   5801,
5807,   5813,   5821,   5827,   5839,   5843,   5849,   5851,   5857,   5861,
5867,   5869,   5879,   5881,   5897,   5903,   5923,   5927,   5939,   5953,
5981,   5987,   6007,   6011,   6029,   6037,   6043,   6047,   6053,   6067,
6073,   6079,   6089,   6091,   6101,   6113,   6121,   6131,   6133,   6143,
6151,   6163,   6173,   6197,   6199,   6203,   6211,   6217,   6221,   6229,
6247,   6257,   6263,   6269,   6271,   6277,   6287,   6299,   6301,   6311,
6317,   6323,   6329,   6337,   6343,   6353,   6359,   6361,   6367,   6373,
6379,   6389,   6397,   6421,   6427,   6449,   6451,   6469,   6473,   6481,
6491,   6521,   6529,   6547,   6551,   6553,   6563,   6569,   6571,   6577,
6581,   6599,   6607,   6619,   6637,   6653,   6659,   6661,   6673,   6679,
6689,   6691,   6701,   6703,   6709,   6719,   6733,   6737,   6761,   6763,
6779,   6781,   6791,   6793,   6803,   6823,   6827,   6829,   6833,   6841,
6857,   6863,   6869,   6871,   6883,   6899,   6907,   6911,   6917,   6947,
6949,   6959,   6961,   6967,   6971,   6977,   6983,   6991,   6997,   7001,
7013,   7019,   7027,   7039,   7043,   7057,   7069,   7079,   7103,   7109,
7121,   7127,   7129,   7151,   7159,   7177,   7187,   7193,   7207,   7211,
7213,   7219,   7229,   7237,   7243,   7247,   7253,   7283,   7297,   7307,
7309,   7321,   7331,   7333,   7349,   7351,   7369,   7393,   7411,   7417,
7433,   7451,   7457,   7459,   7477,   7481,   7487,   7489,   7499,   7507,
7517,   7523,   7529,   7537,   7541,   7547,   7549,   7559,   7561,   7573,
7577,   7583,   7589,   7591,   7603,   7607,   7621,   7639,   7643,   7649,
7669,   7673,   7681,   7687,   7691,   7699,   7703,   7717,   7723,   7727,
7741,   7753,   7757,   7759,   7789,   7793,   7817,   7823,   7829,   7841,
7853,   7867,   7873,   7877,   7879,   7883,   7901,   7907,   7919,   7927,
7933,   7937,   7949,   7951,   7963,   7993,   8009,   8011,   8017,   8039,
8053,   8059,   8069,   8081,   8087,   8089,   8093,   8101,   8111,   8117,
8123,   8147,   8161,   8167,   8171,   8179,   8191,   8209,   8219,   8221,
8231,   8233,   8237,   8243,   8263,   8269,   8273,   8287,   8291,   8293,
8297,   8311,   8317,   8329,   8353,   8363,   8369,   8377,   8387,   8389,
8419,   8423,   8429,   8431,   8443,   8447,   8461,   8467,   8501,   8513,
8521,   8527,   8537,   8539,   8543,   8563,   8573,   8581,   8597,   8599,
8609,   8623,   8627,   8629,   8641,   8647,   8663,   8669,   8677,   8681,
8689,   8693,   8699,   8707,   8713,   8719,   8731,   8737,   8741,   8747,
8753,   8761,   8779,   8783,   8803,   8807,   8819,   8821,   8831,   8837,
8839,   8849,   8861,   8863,   8867,   8887,   8893,   8923,   8929,   8933,
8941,   8951,   8963,   8969,   8971,   8999,   9001,   9007,   9011,   9013,
9029,   9041,   9043,   9049,   9059,   9067,   9091,   9103,   9109,   9127,
9133,   9137,   9151,   9157,   9161,   9173,   9181,   9187,   9199,   9203,
9209,   9221,   9227,   9239,   9241,   9257,   9277,   9281,   9283,   9293,
9311,   9319,   9323,   9337,   9341,   9343,   9349,   9371,   9377,   9391,
9397,   9403,   9413,   9419,   9421,   9431,   9433,   9437,   9439,   9461,
9463,   9467,   9473,   9479,   9491,   9497,   9511,   9521,   9533,   9539,
9547,   9551,   9587,   9601,   9613,   9619,   9623,   9629,   9631,   9643,
9649,   9661,   9677,   9679,   9689,   9697,   9719,   9721,   9733,   9739,
9743,   9749,   9767,   9769,   9781,   9787,   9791,   9803,   9811,   9817,
9829,   9833,   9839,   9851,   9857,   9859,   9871,   9883,   9887,   9901,
9907,   9923,   9929,   9931,   9941,   9949,   9967,   9973,   10007,  10009,
10037,  10039,  10061,  10067,  10069,  10079,  10091,  10093,  10099,  10103,
10111,  10133,  10139,  10141,  10151,  10159,  10163,  10169,  10177,  10181,
10193,  10211,  10223,  10243,  10247,  10253,  10259,  10267,  10271,  10273,
10289,  10301,  10303,  10313,  10321,  10331,  10333,  10337,  10343,  10357,
10369,  10391,  10399,  10427,  10429,  10433,  10453,  10457,  10459,  10463,
10477,  10487,  10499,  10501,  10513,  10529,  10531,  10559,  10567,  10589,
10597,  10601,  10607,  10613,  10627,  10631,  10639,  10651,  10657,  10663,
10667,  10687,  10691,  10709,  10711,  10723,  10729,  10733,  10739,  10753,
10771,  10781,  10789,  10799,  10831,  10837,  10847,  10853,  10859,  10861,
10867,  10883,  10889,  10891,  10903,  10909,  10937,  10939,  10949,  10957,
10973,  10979,  10987,  10993,  11003,  11027,  11047,  11057,  11059,  11069,
11071,  11083,  11087,  11093,  11113,  11117,  11119,  11131,  11149,  11159,
11161,  11171,  11173,  11177,  11197,  11213,  11239,  11243,  11251,  11257,
11261,  11273,  11279,  11287,  11299,  11311,  11317,  11321,  11329,  11351,
11353,  11369,  11383,  11393,  11399,  11411,  11423,  11437,  11443,  11447,
11467,  11471,  11483,  11489,  11491,  11497,  11503,  11519,  11527,  11549,
11551,  11579,  11587,  11593,  11597,  11617,  11621,  11633,  11657,  11677,
11681,  11689,  11699,  11701,  11717,  11719,  11731,  11743,  11777,  11779,
11783,  11789,  11801,  11807,  11813,  11821,  11827,  11831,  11833,  11839,
11863,  11867,  11887,  11897,  11903,  11909,  11923,  11927,  11933,  11939,
11941,  11953,  11959,  11969,  11971,  11981,  11987,  12007,  12011,  12037,
12041,  12043,  12049,  12071,  12073,  12097,  12101,  12107,  12109,  12113,
12119,  12143,  12149,  12157,  12161,  12163,  12197,  12203,  12211,  12227,
12239,  12241,  12251,  12253,  12263,  12269,  12277,  12281,  12289,  12301,
12323,  12329,  12343,  12347,  12373,  12377,  12379,  12391,  12401,  12409,
12413,  12421,  12433,  12437,  12451,  12457,  12473,  12479,  12487,  12491,
12497,  12503,  12511,  12517,  12527,  12539,  12541,  12547,  12553,  12569,
12577,  12583,  12589,  12601,  12611,  12613,  12619,  12637,  12641,  12647,
12653,  12659,  12671,  12689,  12697,  12703,  12713,  12721,  12739,  12743,
12757,  12763,  12781,  12791,  12799,  12809,  12821,  12823,  12829,  12841,
12853,  12889,  12893,  12899,  12907,  12911,  12917,  12919,  12923,  12941,
12953,  12959,  12967,  12973,  12979,  12983,  13001,  13003,  13007,  13009,
13033,  13037,  13043,  13049,  13063,  13093,  13099,  13103,  13109,  13121,
13127,  13147,  13151,  13159,  13163,  13171,  13177,  13183,  13187,  13217,
13219,  13229,  13241,  13249,  13259,  13267,  13291,  13297,  13309,  13313,
13327,  13331,  13337,  13339,  13367,  13381,  13397,  13399,  13411,  13417,
13421,  13441,  13451,  13457,  13463,  13469,  13477,  13487,  13499,  13513,
13523,  13537,  13553,  13567,  13577,  13591,  13597,  13613,  13619,  13627,
13633,  13649,  13669,  13679,  13681,  13687,  13691,  13693,  13697,  13709,
13711,  13721,  13723,  13729,  13751,  13757,  13759,  13763,  13781,  13789,
13799,  13807,  13829,  13831,  13841,  13859,  13873,  13877,  13879,  13883,
13901,  13903,  13907,  13913,  13921,  13931,  13933,  13963,  13967,  13997,
13999,  14009,  14011,  14029,  14033,  14051,  14057,  14071,  14081,  14083,
14087,  14107,  14143,  14149,  14153,  14159,  14173,  14177,  14197,  14207,
14221,  14243,  14249,  14251,  14281,  14293,  14303,  14321,  14323,  14327,
14341,  14347,  14369,  14387,  14389,  14401,  14407,  14411,  14419,  14423,
14431,  14437,  14447,  14449,  14461,  14479,  14489,  14503,  14519,  14533,
14537,  14543,  14549,  14551,  14557,  14561,  14563,  14591,  14593,  14621,
14627,  14629,  14633,  14639,  14653,  14657,  14669,  14683,  14699,  14713,
14717,  14723,  14731,  14737,  14741,  14747,  14753,  14759,  14767,  14771,
14779,  14783,  14797,  14813,  14821,  14827,  14831,  14843,  14851,  14867,
14869,  14879,  14887,  14891,  14897,  14923,  14929,  14939,  14947,  14951,
14957,  14969,  14983,  15013,  15017,  15031,  15053,  15061,  15073,  15077,
15083,  15091,  15101,  15107,  15121,  15131,  15137,  15139,  15149,  15161,
15173,  15187,  15193,  15199,  15217,  15227,  15233,  15241,  15259,  15263,
15269,  15271,  15277,  15287,  15289,  15299,  15307,  15313,  15319,  15329,
15331,  15349,  15359,  15361,  15373,  15377,  15383,  15391,  15401,  15413,
15427,  15439,  15443,  15451,  15461,  15467,  15473,  15493,  15497,  15511,
15527,  15541,  15551,  15559,  15569,  15581,  15583,  15601,  15607,  15619,
15629,  15641,  15643,  15647,  15649,  15661,  15667,  15671,  15679,  15683,
15727,  15731,  15733,  15737,  15739,  15749,  15761,  15767,  15773,  15787,
15791,  15797,  15803,  15809,  15817,  15823,  15859,  15877,  15881,  15887,
15889,  15901,  15907,  15913,  15919,  15923,  15937,  15959,  15971,  15973,
15991,  16001,  16007,  16033,  16057,  16061,  16063,  16067,  16069,  16073,
16087,  16091,  16097,  16103,  16111,  16127,  16139,  16141,  16183,  16187,
16189,  16193,  16217,  16223,  16229,  16231,  16249,  16253,  16267,  16273,
16301,  16319,  16333,  16339,  16349,  16361,  16363,  16369,  16381,  16411,
16417,  16421,  16427,  16433,  16447,  16451,  16453,  16477,  16481,  16487,
16493,  16519,  16529,  16547,  16553,  16561,  16567,  16573,  16603,  16607,
16619,  16631,  16633,  16649,  16651,  16657,  16661,  16673,  16691,  16693,
16699,  16703,  16729,  16741,  16747,  16759,  16763,  16787,  16811,  16823,
16829,  16831,  16843,  16871,  16879,  16883,  16889,  16901,  16903,  16921,
16927,  16931,  16937,  16943,  16963,  16979,  16981,  16987,  16993,  17011,
17021,  17027,  17029,  17033,  17041,  17047,  17053,  17077,  17093,  17099,
17107,  17117,  17123,  17137,  17159,  17167,  17183,  17189,  17191,  17203,
17207,  17209,  17231,  17239,  17257,  17291,  17293,  17299,  17317,  17321,
17327,  17333,  17341,  17351,  17359,  17377,  17383,  17387,  17389,  17393,
17401,  17417,  17419,  17431,  17443,  17449,  17467,  17471,  17477,  17483,
17489,  17491,  17497,  17509,  17519,  17539,  17551,  17569,  17573,  17579,
17581,  17597,  17599,  17609,  17623,  17627,  17657,  17659,  17669,  17681,
17683,  17707,  17713,  17729,  17737,  17747,  17749,  17761,  17783,  17789,
17791,  17807,  17827,  17837,  17839,  17851,  17863,  17881,  17891,  17903,
17909,  17911,  17921,  17923,  17929,  17939,  17957,  17959,  17971,  17977,
17981,  17987,  17989,  18013,  18041,  18043,  18047,  18049,  18059,  18061,
18077,  18089,  18097,  18119,  18121,  18127,  18131,  18133,  18143,  18149,
18169,  18181,  18191,  18199,  18211,  18217,  18223,  18229,  18233,  18251,
18253,  18257,  18269,  18287,  18289,  18301,  18307,  18311,  18313,  18329,
18341,  18353,  18367,  18371,  18379,  18397,  18401,  18413,  18427,  18433,
18439,  18443,  18451,  18457,  18461,  18481,  18493,  18503,  18517,  18521,
18523,  18539,  18541,  18553,  18583,  18587,  18593,  18617,  18637,  18661,
18671,  18679,  18691,  18701,  18713,  18719,  18731,  18743,  18749,  18757,
18773,  18787,  18793,  18797,  18803,  18839,  18859,  18869,  18899,  18911,
18913,  18917,  18919,  18947,  18959,  18973,  18979,  19001,  19009,  19013,
19031,  19037,  19051,  19069,  19073,  19079,  19081,  19087,  19121,  19139,
19141,  19157,  19163,  19181,  19183,  19207,  19211,  19213,  19219,  19231,
19237,  19249,  19259,  19267,  19273,  19289,  19301,  19309,  19319,  19333,
19373,  19379,  19381,  19387,  19391,  19403,  19417,  19421,  19423,  19427,
19429,  19433,  19441,  19447,  19457,  19463,  19469,  19471,  19477,  19483,
19489,  19501,  19507,  19531,  19541,  19543,  19553,  19559,  19571,  19577,
19583,  19597,  19603,  19609,  19661,  19681,  19687,  19697,  19699,  19709,
19717,  19727,  19739,  19751,  19753,  19759,  19763,  19777,  19793,  19801,
19813,  19819,  19841,  19843,  19853,  19861,  19867,  19889,  19891,  19913,
19919,  19927,  19937,  19949,  19961,  19963,  19973,  19979,  19991,  19993,
19997,  20011,  20021,  20023,  20029,  20047,  20051,  20063,  20071,  20089,
20101,  20107,  20113,  20117,  20123,  20129,  20143,  20147,  20149,  20161,
20173,  20177,  20183,  20201,  20219,  20231,  20233,  20249,  20261,  20269,
20287,  20297,  20323,  20327,  20333,  20341,  20347,  20353,  20357,  20359,
20369,  20389,  20393,  20399,  20407,  20411,  20431,  20441,  20443,  20477,
20479,  20483,  20507,  20509,  20521,  20533,  20543,  20549,  20551,  20563,
20593,  20599,  20611,  20627,  20639,  20641,  20663,  20681,  20693,  20707,
20717,  20719,  20731,  20743,  20747,  20749,  20753,  20759,  20771,  20773,
20789,  20807,  20809,  20849,  20857,  20873,  20879,  20887,  20897,  20899,
20903,  20921,  20929,  20939,  20947,  20959,  20963,  20981,  20983,  21001,
21011,  21013,  21017,  21019,  21023,  21031,  21059,  21061,  21067,  21089,
21101,  21107,  21121,  21139,  21143,  21149,  21157,  21163,  21169,  21179,
21187,  21191,  21193,  21211,  21221,  21227,  21247,  21269,  21277,  21283,
21313,  21317,  21319,  21323,  21341,  21347,  21377,  21379,  21383,  21391,
21397,  21401,  21407,  21419,  21433,  21467,  21481,  21487,  21491,  21493,
21499,  21503,  21517,  21521,  21523,  21529,  21557,  21559,  21563,  21569,
21577,  21587,  21589,  21599,  21601,  21611,  21613,  21617,  21647,  21649,
21661,  21673,  21683,  21701,  21713,  21727,  21737,  21739,  21751,  21757,
21767,  21773,  21787,  21799,  21803,  21817,  21821,  21839,  21841,  21851,
21859,  21863,  21871,  21881,  21893,  21911,  21929,  21937,  21943,  21961,
21977,  21991,  21997,  22003,  22013,  22027,  22031,  22037,  22039,  22051,
22063,  22067,  22073,  22079,  22091,  22093,  22109,  22111,  22123,  22129,
22133,  22147,  22153,  22157,  22159,  22171,  22189,  22193,  22229,  22247,
22259,  22271,  22273,  22277,  22279,  22283,  22291,  22303,  22307,  22343,
22349,  22367,  22369,  22381,  22391,  22397,  22409,  22433,  22441,  22447,
22453,  22469,  22481,  22483,  22501,  22511,  22531,  22541,  22543,  22549,
22567,  22571,  22573,  22613,  22619,  22621,  22637,  22639,  22643,  22651,
22669,  22679,  22691,  22697,  22699,  22709,  22717,  22721,  22727,  22739,
22741,  22751,  22769,  22777,  22783,  22787,  22807,  22811,  22817,  22853,
22859,  22861,  22871,  22877,  22901,  22907,  22921,  22937,  22943,  22961,
22963,  22973,  22993,  23003,  23011,  23017,  23021,  23027,  23029,  23039,
23041,  23053,  23057,  23059,  23063,  23071,  23081,  23087,  23099,  23117,
23131,  23143,  23159,  23167,  23173,  23189,  23197,  23201,  23203,  23209,
23227,  23251,  23269,  23279,  23291,  23293,  23297,  23311,  23321,  23327,
23333,  23339,  23357,  23369,  23371,  23399,  23417,  23431,  23447,  23459,
23473,  23497,  23509,  23531,  23537,  23539,  23549,  23557,  23561,  23563,
23567,  23581,  23593,  23599,  23603,  23609,  23623,  23627,  23629,  23633,
23663,  23669,  23671,  23677,  23687,  23689,  23719,  23741,  23743,  23747,
23753,  23761,  23767,  23773,  23789,  23801,  23813,  23819,  23827,  23831,
23833,  23857,  23869,  23873,  23879,  23887,  23893,  23899,  23909,  23911,
23917,  23929,  23957,  23971,  23977,  23981,  23993,  24001,  24007,  24019,
24023,  24029,  24043,  24049,  24061,  24071,  24077,  24083,  24091,  24097,
24103,  24107,  24109,  24113,  24121,  24133,  24137,  24151,  24169,  24179,
24181,  24197,  24203,  24223,  24229,  24239,  24247,  24251,  24281,  24317,
24329,  24337,  24359,  24371,  24373,  24379,  24391,  24407,  24413,  24419,
24421,  24439,  24443,  24469,  24473,  24481,  24499,  24509,  24517,  24527,
24533,  24547,  24551,  24571,  24593,  24611,  24623,  24631,  24659,  24671,
24677,  24683,  24691,  24697,  24709,  24733,  24749,  24763,  24767,  24781,
24793,  24799,  24809,  24821,  24841,  24847,  24851,  24859,  24877,  24889,
24907,  24917,  24919,  24923,  24943,  24953,  24967,  24971,  24977,  24979,
24989,  25013,  25031,  25033,  25037,  25057,  25073,  25087,  25097,  25111,
25117,  25121,  25127,  25147,  25153,  25163,  25169,  25171,  25183,  25189,
25219,  25229,  25237,  25243,  25247,  25253,  25261,  25301,  25303,  25307,
25309,  25321,  25339,  25343,  25349,  25357,  25367,  25373,  25391,  25409
};

class BigNum
{
      public:
          int length;   //大数长度
          int signal;   //大数符号
          unsigned long array[len1];   //大数绝对值 
              
          BigNum();   //构造函数 
          BigNum(unsigned __int64);    //构造函数用于赋初始值  
          BigNum(string s);   //读入字符串
          BigNum(BigNum const& A);   //复制大数，const保护了原对象的属性 
          ~BigNum();   //析构函数
      
          BigNum operator+(BigNum & A);   //运算符+重载
          BigNum operator-(BigNum & A);   //运算符-重载
          BigNum operator*(BigNum & A);   //运算符*重载
          BigNum operator/(BigNum & A);   //运算符/重载
          BigNum operator%(BigNum & A);   //运算符%重载
          BigNum operator-(void);   //负号重载
          int operator==(BigNum& A);   //等于号重载
          int operator!=(BigNum& A);   //不等号重载
          int Compare(BigNum const& A);    //比较两大数绝对值大小
          void GeneratePrime(void);   //产生素数
          int Rabin_Miller(void);   //拉宾米勒算法用于素数测试
          void Random(int a);   //随机产生一个大数
          void Random(BigNum A);   //随机产生一个小于A的大数
          void print(void);   //输出大数 
          void printS(void);   //输出字符串
          BigNum power_mod(BigNum& A, BigNum& B);   //模幂算法计算X^A mod B
          BigNum ex_euclid(BigNum a,BigNum b);   //扩展欧几里德算法
};

/*构造函数*/ 
BigNum::BigNum()
{
      length=1;
      signal=0;
      for(int i=0;i<len1;i++)
          array[i]=0;
}

/*构造函数用于赋初始值,参数为64位无符号int*/ 
BigNum::BigNum(unsigned __int64 A)
{    
    signal=0;
	if(A<=0xffffffff){ 
        length=1;
		array[0]=(unsigned long)A;                    
	}
	else{
        length=2;	//长度大于1，存两位	
		array[1]=(unsigned long)(A>>32);
		array[0]=(unsigned long)A;
	}
	for(int i=length;i<len1;i++)  //补充高位 
        array[i]=0;
}

/*用于读入输入的要加密的字符串，大数的每一位是32位，可以存4个字符*/
BigNum::BigNum(string s)
{
   for(int i=0;i<s.size();i++){
       array[i/4]<<=8;       
       array[i/4]|=s[i];   //按位或，将4个字符存到一个大数位里
   }
   length=(s.size()-1)/4+1;   //数组长度 
}

/*用于复制大数*/ 
BigNum::BigNum(BigNum const& A)
{
      length=A.length;
      signal=A.signal;
      for(int i=0;i<len1;i++)
          array[i]=A.array[i];
}

/*析构函数,撤销对象占用的内存之前完成一些清理工作*/
BigNum::~BigNum()                   
{}

/*运算符+重载，思路：两数符号相同时，和=加数当前位+被加数当前位+进位；
两位异号时，转化为减法运算*/ 
BigNum BigNum::operator+(BigNum& A)
{
      BigNum SUM,D;   //B为两大数之和，D为中间变量
      int C=0;    //进位  
      unsigned __int64 sum;   //存储int型的和
      
      if(signal==A.signal){     //符号相同时 
         SUM.signal=signal;                 
         if(length>=A.length)    //长度=两数最大长度+1 
            SUM.length=length+1;
         else 
            SUM.length=A.length+1;
         for(int i=0;i<SUM.length;i++){    //和=加数当前位+被加数当前+进位 
             sum=(unsigned __int64)A.array[i]+(unsigned __int64)array[i]+C;
             if(sum<=0xffffffff) 
                 C=0;     //超过2^32-1,进位 
             else 
                 C=1;           
             SUM.array[i]=(unsigned long)sum;   //和当前位= (unsigned long)和 
         }
         while(SUM.length>1)    //消除最高位的0 
            if(SUM.array[SUM.length-1]==0)                
               SUM.length--;
            else break;             
      }
      else if(signal==0){
              D=-A;
              SUM=(*this)-D;
           }    //异号则转为减法运算 
           else{
              D=-(*this);
              SUM=A-D; 
           } 
      return  SUM;      
} 
      
/*运算符-重载，思路：两数同号时，比较两数大小，被减数大时，如果sub=被减数当前位-上一个
借位小于减数当前位，那么当前位有借位，差=借位*0xffffffff+sub-减数当前位+借位；减数大时，
原理一样，交换减数和被减数位置，最后负号与被减数相反；两数异号时，转化成加法运算*/
BigNum BigNum::operator-(BigNum& A)
{
      BigNum SUB,D;   //B为两数的差，D为中间变量
      int F=0,i;     //借位F 
      unsigned int sub;   //暂存被减数减去上一个借位的差
      
      if(signal==A.signal){    //符号相同时 
         if(Compare(A)==0||Compare(A)==2){    //当被减数大于等于减数  
            if(signal==0) 
                SUB.signal=0;      //符号判断 
            else  
                SUB.signal=1;        
            for(i=0;i<length;i++){
               sub=array[i]-F;    //差=被减数当前位-上一个借位  
               if(sub<A.array[i])
                   F=1;    //如果差小于减数当前位 ,有借位 
               else 
                   F=0;                           
               SUB.array[i]=0xffffffff*F-A.array[i]+sub+F; //差的当前位 
            } 
         }       
         else{       //被减数小于减数,基本原理同上 
            if(signal==0)    //符号判断
                SUB.signal=1;    
            else  
                SUB.signal=0; 
            for(i=0;i<A.length;i++){
                sub=A.array[i]-F;                    
                if(sub<array[i]) 
                    F=1;   //向上借位
                else 
                    F=0;
                SUB.array[i]=0xffffffff*F-array[i]+sub+F; 
            }      
         }  
         SUB.length=i;        
         while(SUB.length>1)     //消除最高位的0 
              if(SUB.array[SUB.length-1]==0)                
                 SUB.length--;
              else break;         
     }      
     else{   ////如果异号,转为加法
         D=-A;
         SUB=(*this)+D;
     }       
     return SUB;
}

/*运算符*重载，思路：两数同号时，积的符号为正，否则为负，积=当前位的积+进位*/ 
BigNum BigNum::operator*(BigNum& A)
{
      BigNum PRO;   //B两大数的积
      unsigned __int64 C=0;      //进位C  
      unsigned __int64 pro;   //暂存两数当前位的积 
      
      if(signal==A.signal)     //判断符号 
           PRO.signal=0;   
       else 
           PRO.signal=1;
      PRO.length=length+A.length;       //长度不超过两数长度和 
      for(int i=0;i<A.length;i++) {    
          for(int j=0;j<=length;j++){      //积=当前位的乘积+进位 
              pro=(unsigned __int64)A.array[i]*(unsigned __int64)array[j]+C;
              if((unsigned __int64)PRO.array[i+j]+pro>0xffffffff)   //判断有无进位
                 C=((unsigned __int64)PRO.array[i+j]+pro)>>32;
              else 
                 C=0;         
              PRO.array[i+j]+=(unsigned long)pro;   //当前位要加上上一次运算结果 
          } 
       } 
       while(PRO.length>1)      //消除最高位的0 
           if(PRO.array[PRO.length-1]==0)                
               PRO.length--;
           else break;  
       return PRO;   
}

/*运算符/重载，思路：采用试商法，取被除数最高位（如果小于除数最高位则去前两位）
和除数最高位试商，商=被除数最高位/（除数最高位+1），余数=被除数-商*除数，将余数
作为新的被除数做下次运算，每次运算完商都移位，直到余数小于等于除数，等于除数时商+1，
单独考虑除数长度为1的情况*/ 
BigNum BigNum::operator/(BigNum& A) 
{
    
    BigNum X(*this),Y,Z,I(1);
    int i,len;   //len移位
    unsigned __int64 temp,div,mul;
    unsigned long F=0; //余数 
    
    if(A.length>1){      //除数长度大于1时   
        while(X.Compare(A)==0){     //当被除数大于除数时 
            if(X.array[X.length-1]>A.array[A.length-1]){   //被除数最高位大 
		        len=X.length-A.length;   //商=被除数当前位/(除数当前位+1) 
		        div=X.array[X.length-1]/(A.array[A.length-1]+1);
            }
		    else if(X.length>A.length){     //被除数长度较长 
		             len=X.length-A.length-1;
                     temp=X.array[X.length-1];         
                     temp=(temp<<32)+X.array[X.length-2]; //商=被除数前两位/(除数当前位+1) 
                     if(A.array[A.length-1]==0xffffffff)div=(temp>>32);
                     else div=temp/(A.array[A.length-1]+1);
                 }
                 else{      //相等,加1退出  
                     Y=Y+I;
                     break;
                 }                 
		    Z=BigNum(div);      //暂时的商(大数) 
		    Z.length+=len;      //长度=原长+移位 
		    for(i=Z.length-1;i>=len;i--)
                Z.array[i]=Z.array[i-len];
		    for(i=0;i<len;i++)
                Z.array[i]=0;
		    Y=Y+Z;      //商=原商+暂商 
		    Z=A*Z;                           
            X=X-Z;   //求余数代入下一次运算
        }       
        if(X.Compare(A)==2)
            Y=Y+I;     //相等+1返回 
        if(signal!=A.signal)
            Y.signal=1;     //判断符号，异号为负 
        return Y;
    }
    else{    //除数长度等于1 
        if(X.length==1)     //被除数长度也为1 
            X.array[0]=X.array[0]/A.array[0];
        else{
            for(int i=X.length-1;i>=0;i--){
               div=F;                     
               div=(div<<32)+X.array[i];    //被除数=余数+当前位 
               X.array[i]=(unsigned long)(div/A.array[0]);   //商
               mul=(div/A.array[0])*A.array[0];
               F=(unsigned long)(div-mul);  //求余,再带入下次运算 
            }
            if(X.array[X.length-1]==0)
               X.length--;
        }   
       return X;
    }
}

/*重载运算符之求模，思路同除法重载*/
BigNum BigNum::operator%(BigNum& A)
{ 
    BigNum Y(*this),Z,T;
    int i,len;
    unsigned __int64 temp,div,F=0;
             
    if(A.length>1) {       //除数长度大于1时 
        while(Y.Compare(A)==0||Y.Compare(A)==2){     //被除数大等于除数 
            div=Y.array[Y.length-1];     // 被除数=被除数当前位 
		    temp=A.array[A.length-1];     // 除数=除数当前位 
		    len=Y.length-A.length;    //移位 
		    if((div==temp)&&(len==0)){      //长度相同首位相同,余数为差 
                Y=Y-A;break;
            }                       
		    if((div<=temp)&&length){      //被除数小于除数，被除数取前两位 
                len--;
                div=(div<<32)+Y.array[Y.length-2];
            }
		    div=div/(temp+1);    //下面原理同除法重载
		    Z=BigNum(div);
		    if(len){
			    Z.length+=len;
			    for(i=Z.length-1;i>=len;i--)Z.array[i]=Z.array[i-len];
			    for(i=0;i<len;i++)Z.array[i]=0;
            }
		    T=A*Z;
            Y=Y-T;
        }
        return Y;
    }
	else{      //除数长度等于1时       
        if(length==1) 
            F=array[0]%A.array[0];
        else	     
	        for(int i=length-1;i>=0;--i){
		        F=(F<<32)|array[i];
                F%=A.array[0];
            }
        return BigNum(F); 
    }
}

/*负号重载 */  
BigNum BigNum::operator-(void)
{
      BigNum Temp=*this;
      Temp.signal=1-signal;
      return Temp;
} 

/*等于号重载 */ 
int BigNum::operator==(BigNum& A)
{   
    if(signal==A.signal)   //判断符号
       return Compare(A)==2;    //绝对值相等则返回两数相等
    else
       return 0;   
}

/*不等号重载*/
int BigNum::operator!=(BigNum& A)
{   if(signal==A.signal)
       return Compare(A)!=2; 
    else
       return 0; 
} 
      
/* 比较两大数绝对值大小，1表示小于A，0表示大于A，2表示相等*/ 
int BigNum::Compare(BigNum const& A)  
{                                           
     if(length>A.length)      //比较长度 
         return 0;
     else if(length<A.length) 
         return 1;
     else{
         for(int i=length-1;i>=0;i--){
            if(array[i]>A.array[i])
               return 0;
            else if(array[i]<A.array[i])
               return 1;
         }
         return 2;   //相等
    }    
} 

/*随机产生一个大数0<=X<=2^(32*SLEN)-1*/ 
void BigNum::Random(int a)
{
     int i;
     
     signal=a;   //a传入的一般都是0 
     length=len2;  
     for(i=0;i<len2;++i)   //rand产生0-32767的数（16位长），两次生成随机数移位后的和 
         array[i]=rand()<<16 | rand(); 
     array[len2-1] |=1<<31;  //确保大数为512位长                  
}

/*随机产生一个小于A的大数*/
void BigNum::Random(BigNum A)
{
     int i;
     
     signal=0;   
     if(A.length>1){     //被比较数长度为1时仅生成1位 
         length=A.length-1;      
         for(i=0;i<length;++i)
             array[i]=rand()<<16 | rand();
     } 
     else{      //生成的位数少于被比较数 
         length=1;
         array[0]=rand()<<16 | rand(); 
         while(array[0]>A.array[0])
             array[0]=rand()<<16 | rand();
    }                        
}

/*拉宾米勒算法用于素数测试，思路：1、先和前1000个素数比较，提高判断效率；2、计算
r和m使得n-1=(2^r)*m；3、随机选择a，计算y=a^m(mod n)；4、如果y=1或者y=n-1，输出素数，
结束；5、for i=1 to r-1, y=y^2(mod n)，若y=1,输出合数，结束，否则i++；6、若y!=n-1,
输出合数，结束。*/  
int BigNum::Rabin_Miller(void)
{
    BigNum temp,X(*this),I(1),O(0),m,E(2),A,Y,T,C;
    int r=0;
    
    for(int i=0;i<2800;i++){     //被判断数先除以2800个小素数提高效率 
        temp=BigNum(Primes[i]);
        if(X==temp)
            return 1;   //素数
        if(X%temp==O){   //合数
            return 0;
        }
    }
    m=*this-I;    //Y=被判断数-1 
    while(!(m.array[0] & 1)){     //Y非奇数 
	    r++;                                
	    m=m/E;
    }      //求得r,Y，满足X-1=(2^r)*Y 
    for(int i=1;i<=5;++i){     //由于一次判断不是素数的概率小等于1/4
       int flag=0;     //所以至少要进行5次判断以确保准确性    
       A.Random(X);                          //随机生成小于被判断数的数 
       while(A.Compare(T)==2) A.Random(X);   //和上次避免产生相同的A 
       T=A;      
       Y=A.power_mod(m,X);                          // B=A^Y mod X  
       if((O.Compare((Y-I)%X)==2)|| (O.Compare((Y+I)%X)==2))                                       
           continue;                         //若B=1或X-1，则是素数   
       else{
           for(int j=0;j<r;j++){
              Y=(Y*Y)%X;                     //否则,B=b^2%X 
              if(O.Compare((Y+I)%X)==2){     //B=1,则是合数     
                 flag=1;
                 break;
              }   
           }
       }
       if(flag)                             
          continue;
       else                                    
          return 0;
    }       
    return 1;    
}
            
/*产生 512 位的素数*/ 
void BigNum::GeneratePrime(void)
{
   Random(0);   //确保符号为正
   array[0] |= 1;     //确保是奇数以提高效率 
   while(!Rabin_Miller()){          
      Random(0); 
      array[0] |= 1;
   }     
} 
           
/*输出大数*/
void BigNum::print(void)
{   
   cout<<hex;     //以十六进制打印
   for(int i=1;i<=length;++i){
      if(i%8 == 1) 
          cout<<endl;   //换行，8个数组元素一行 
      cout<<setw(8)<<array[length-i]<<" ";
   }
   cout<<dec<<endl;
} 

/*输出字符串，每一个array[i]存4个字符，每一次右移8位去出一个字符*/   
void BigNum::printS(void)                        
{
   for(int i=0;i<=length;++i)
      for(int j=3;j>=0;--j){
         char chr=char(array[i]>>(j*8));   //右移8位取一个字符 
         if(chr) cout<<chr;   //是字符输出 
      }
   cout<<endl;
}

/*求Y，使得X^A mod B=Y */  
BigNum BigNum::power_mod(BigNum& A, BigNum& B)
{
   BigNum X(1),N=(*this)%B;

   for(int i=0;i<A.length;i++){ 
       for(int j=0;j<32;j++){     //转为2进制运算提高效率 
          if(A.array[i]&(1<<j))
             X=(X*N)%B;
          N=(N*N)%B;
       }
    }    
    return X;  
} 
  
/*扩展欧几里德算法，求X使得AX mod B=1*/ 
BigNum BigNum::ex_euclid(BigNum a,BigNum b)
{
     BigNum X(1),U(0),O(0),A(a),B(b);   //A，B为了避免修改a，b的值 
     
     while(B!=O){
         BigNum Q(A/B),R(A%B),Temp;
         Temp=Q*U;
         Temp=X-Temp;
         X=U;
         U=Temp;
         A=B;
         B=R;
     }
     if(X.signal==1){    //负数时加上mod 的数b       
        X=X+b;
     }
     *this=X;   //传给当前大数 
     return *this;
}  
   
